package chapter6;

/**
 * 堆排序
 * <p>
 * 原址排序-最坏/平均O(nlgn)
 */
public class HeapSort {

    public static int size = 0;

    /**
     * A[0] 是树根,对于大顶堆来说一定是最大的,所以没步骤往后放
     * <p>
     * 缩减 size 让已经排序好的树根不在参与重建堆
     *
     * @param A
     */
    public static void heapSort(int[] A) {
        buildMaxHeap(A);
        for (int i = A.length - 1; i >= 1; i--) {
            int temp = A[i];
            A[i] = A[0];
            A[0] = temp;

            size--;

            maxHeap(A, 0);
        }
    }

    /**
     * 大顶堆的是父节点要比子节点大
     *
     * @param A
     */
    public static void buildMaxHeap(int[] A) {
        // 按照性质,父节点都在根节点的左边,遍历所有父节点,逐步建堆
        for (int i = parent(size - 1); i >= 0; i--) {
            maxHeap(A, i);
        }
    }

    public static void maxHeap(int[] A, int i) {
        int l = left(i);
        int r = right(i);

        // 左孩子、父节点、右孩子谁是最大值
        int largest;
        if (l <= size - 1 && A[l] > A[i]) {
            largest = l;
        } else {
            largest = i;
        }
        if (r <= size - 1 && A[r] > A[largest]) {
            largest = r;
        }
        // 最大值如果是自身就是叶子节点,如果不是则逐级递减并与父节点值进行交换
        if (largest != i) {
            int temp = A[i];
            A[i] = A[largest];
            A[largest] = temp;

            maxHeap(A, largest);
        }

    }

    public static void buildMinHeap(int[] A) {
        for (int i = parent(size - 1); i >= 0; i--) {
            minHeap(A, i);
        }
    }

    public static void minHeap(int[] A, int i) {
        int l = left(i);
        int r = right(i);

        int least;
        if (l <= size - 1 && A[l] < A[i]) {
            least = l;
        } else {
            least = i;
        }
        if (r <= size - 1 && A[r] < A[least]) {
            least = r;
        }
        if (least != i) {
            int temp = A[i];
            A[i] = A[least];
            A[least] = temp;

            minHeap(A, least);
        }

    }

    /**
     * 按数组顺序构建二叉树时候的父节点位置
     *
     * @param i
     * @return
     */
    public static int parent(int i) {
        return i / 2;
    }

    /**
     * 按数组顺序构建二叉树时候的左孩子位置
     *
     * @param i
     * @return
     */
    public static int left(int i) {
        return 2 * i;
    }

    /**
     * 按数组顺序构建二叉树时候的右孩子位置
     *
     * @param i
     * @return
     */
    public static int right(int i) {
        return 2 * i + 1;
    }

}
